package wcc.engineeringAdmission;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class UserMainCode {
	public static String[] output1;
	
	private static class Student {
		int id, region, marks, prefInd = 0, instRegion;
		int[] prefs;
		
		public Student(int id, int region, int marks, int[] prefs) {
			this.id = id;
			this.region = region;
			this.marks = marks;
			this.prefs = prefs;
		}
		
		public String toString() {
			return "(" + id + ", " + region + ", " + marks + ", " + prefs + ", " + instRegion + ", " + prefInd + ")";
		}
	}
	
	private static class InstitutePreferenceComparator implements Comparator<Student> {
		int region;
		public InstitutePreferenceComparator(int region) {
			this.region = region;
		}
		
		@Override
		public int compare(Student student1, Student student2) {
			if(student1.region == region) {
				if(student2.region == region)
					return student1.marks >= student2.marks ? -1 : 1;
				else
					return student1.marks > student2.marks * 0.7 ? -1 : 1;
			} else if(student2.region == region)
				return student2.marks > student1.marks * 0.7 ? 1 : -1;
			else
				return student1.marks >= student2.marks ? -1 : 1;
		}
	}
	
	private static class Institute {
		int region, numSeats;
		List<Student> students = new ArrayList<Student>(), preferences;
		InstitutePreferenceComparator prefComp;
		
		public Institute(int region, int numSeats, List<Student> preferences) {
			this.region = region;
			this.numSeats = numSeats;
			this.preferences = preferences;
			this.prefComp = new InstitutePreferenceComparator(region);
		}
		
		public boolean isFilled() {
			return students.size() >= numSeats;
		}
		
		public String toString() {
			return "(" + region + ", " + numSeats + ", " + students + ")";
		}
		
		public Student getWorstStudent() {
			int worstInd = -1;
			Student worstStudent = null;
			for(Student student : students) {
				int prefInd = preferences.indexOf(student);
				if(prefInd > worstInd) {
					worstInd = prefInd;
					worstStudent = student;
				}
			}
			return worstStudent;
		}
		
		public boolean prefers(Student student1, Student student2) {
			return prefComp.compare(student1, student2) < 0;
		}
	}
	
	private static String[] splitMatchBrace(String str, char c) {
		int s = 0, count = 0;
		List<String> strs = new ArrayList<String>();
		for(int i = 0; i < str.length(); i++) {
			if(str.charAt(i) == c && count <= 0) {
				strs.add(str.substring(s, i));
				s = i + 1;
			}
			else if(str.charAt(i) == '(')
				count++;
			else if(str.charAt(i) == ')')
				count--;
		}
		strs.add(str.substring(s, str.length()));
		return strs.toArray(new String[strs.size()]);
	}
	
	private static HashMap<Integer, List<Student>> groupByRegion(Student[] students) {
		HashMap<Integer, List<Student>> groups = new HashMap<Integer, List<Student>>();
		for(int i = 0; i < students.length; i++) {
			for(int j = 0; j < students[i].prefs.length; j++) {
				List<Student> list = groups.get(students[i].prefs[j]);
				if(list == null) {
					list = new ArrayList<Student>();
					groups.put((Integer)students[i].prefs[j], list);
				}
				list.add(students[i]);
			}
		}
		for(Integer key : groups.keySet())
			Collections.sort(groups.get(key), new InstitutePreferenceComparator(key));
		return groups;
	}
	
	private static void allocate(List<Student> students, HashMap<Integer, Institute> institutes) {
		for(int studentInd = 0; studentInd < students.size();) {
			Student student = students.get(studentInd);
			if(student.prefInd >= student.prefs.length) {
				studentInd++;
				continue;
			}
			Integer region = (Integer)student.prefs[student.prefInd++];
			Institute institute = institutes.get(region);
			if(!institute.isFilled()) {
				student.instRegion = region;
				institute.students.add(student);
				students.remove(studentInd);
			} else {
				Student worstStudent = institute.getWorstStudent();
				if(worstStudent != null && institute.prefers(student, worstStudent)) {
					students.add(worstStudent);
					worstStudent.instRegion = 0;
					institute.students.remove(worstStudent);
					institute.students.add(student);
					student.instRegion = region;
					students.remove(studentInd);
				}
			}
		}
	}
	
	public static void GetStudentCount(int input1, String input2) {
		String[] inputs = splitMatchBrace(input2, ',');
		output1 = new String[input1];
		for(int tc = 0; tc < inputs.length; tc++) {
			String[] toks = splitMatchBrace(inputs[tc].substring(1, inputs[tc].length() - 1), ',');
			int N = Integer.parseInt(toks[0]);
			String[] nToks = splitMatchBrace(toks[2].substring(1, toks[2].length() - 1), ',');
			Student[] students = new Student[N];
			for(int i = 0; i < N; i++) {
				String[] studentToks = splitMatchBrace(nToks[i].substring(1, nToks[i].length() - 1), ',');
				int numPrefs = Integer.parseInt(studentToks[2]);
				String[] sPrefs = studentToks[3].substring(1, studentToks[3].length() - 1).split(",");
				int[] prefs = new int[numPrefs];
				for(int j = 0; j < numPrefs; j++)
					prefs[j] = Integer.parseInt(sPrefs[j]);
				students[i] = new Student(i, Integer.parseInt(studentToks[0]), Integer.parseInt(studentToks[1]), prefs);
			}
			HashMap<Integer, List<Student>> groups = groupByRegion(students);
			String[] mToks = splitMatchBrace(toks[3].substring(1, toks[3].length() - 1), ',');
			HashMap<Integer, Institute> institutes = new HashMap<Integer, Institute>();
			for(int i = 0; i < Integer.parseInt(toks[1]); i++) {
				String[] instToks = mToks[i].substring(1, mToks[i].length() - 1).split(",");
				int region = Integer.parseInt(instToks[0]);
				institutes.put(region, new Institute(region, Integer.parseInt(instToks[1]), groups.get(region)));
			}
			allocate(new ArrayList<Student>(Arrays.asList(students)), institutes);
			output1[tc] = "";
			for(Student student : students)
				output1[tc] += student.instRegion;
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String input = "9:(61,13,((2,97,9,(1,2,8,8,2,4,8,6,4)),(9,55,4,(6,2,2,8)),(3,41,6,(3,3,2,8,3,3)),(9,49,1,(8)),(2,86,9,(7,9,6,1,8,7,2,2,6)),(6,68,7,(6,2,9,4,6,2,1)),(9,95,3,(1,9,1)),(7,70,4,(3,4,5,2)),(9,64,1,(4)),(2,93,2,(7,2)),(7,59,3,(6,2,9)),(8,96,7,(6,8,7,5,3,7,6)),(5,29,7,(8,4,9,3,1,8,7)),(5,44,7,(8,9,9,4,9,1,6)),(6,34,1,(7)),(1,57,9,(6,7,2,7,5,5,2,8,4)),(3,22,6,(7,5,2,7,1,2)),(2,36,6,(7,1,9,7,9,8)),(9,83,8,(9,4,8,4,1,5,8,2)),(2,47,1,(8)),(4,85,4,(4,6,7,1)),(6,35,8,(3,9,9,9,8,4,4,8)),(4,37,2,(8,4)),(1,77,6,(9,3,8,9,4,1)),(6,84,5,(1,2,9,6,2)),(7,27,8,(3,2,2,8,5,9,5,6)),(2,45,4,(7,2,2,7)),(1,58,9,(8,7,6,3,6,3,4,1,6)),(1,65,6,(6,8,5,5,1,8)),(2,92,9,(4,8,8,6,2,5,7,9,7)),(2,38,5,(5,8,5,3,1)),(2,91,5,(8,2,4,2,3)),(9,90,5,(9,1,6,8,4)),(4,89,6,(9,1,2,9,7,5)),(3,48,4,(9,7,1,2)),(4,52,9,(6,5,2,7,8,9,3,5,1)),(9,53,6,(4,7,9,8,6,3)),(8,31,3,(8,4,8)),(6,43,6,(1,2,9,2,9,4)),(9,82,3,(2,4,2)),(2,99,8,(8,7,3,2,1,1,9,7)),(2,25,1,(3)),(9,33,7,(3,3,4,3,9,8,7)),(7,79,4,(7,5,5,2)),(8,63,8,(3,6,8,3,5,5,1,6)),(9,74,2,(5,7)),(1,88,5,(4,8,4,5,3)),(2,61,6,(1,3,2,2,2,9)),(7,81,7,(5,3,5,6,7,5,3)),(9,56,8,(8,4,1,2,4,2,9,2)),(6,24,6,(2,1,7,6,1,3)),(8,50,9,(2,5,5,7,3,8,9,7,4)),(5,26,3,(4,9,5)),(9,60,2,(4,3)),(9,54,4,(4,4,4,8)),(7,66,2,(3,8)),(7,69,9,(9,3,3,8,7,1,6,2,8)),(3,76,9,(2,7,8,1,3,1,9,7,5)),(8,21,7,(4,7,4,4,2,7,9)),(7,32,3,(3,5,6)),(9,72,4,(8,5,9,8))),((1,7),(2,1),(3,1),(4,5),(5,8),(6,2),(7,5),(8,3),(9,1),(10,8),(11,9),(12,3),(13,9)))" +
				",(30,18,((1,81,8,(6,3,6,5,9,4,2,6)),(1,75,7,(9,3,7,4,5,1,7)),(1,63,1,(3)),(9,45,1,(7)),(1,57,5,(5,1,9,3,6)),(2,92,4,(2,5,6,9)),(9,33,3,(5,8,5)),(6,61,4,(8,9,1,3)),(9,97,4,(8,6,9,2)),(6,93,9,(2,3,5,6,1,5,8,4,2)),(9,28,5,(5,9,2,8,9)),(5,69,9,(1,3,9,3,8,1,4,3,1)),(7,96,7,(9,2,1,9,5,1,4)),(7,68,9,(8,6,1,2,1,9,6,4,1)),(1,85,3,(9,9,1)),(5,83,5,(8,8,5,7,7)),(7,74,5,(3,6,3,1,8)),(7,55,4,(5,4,6,5)),(9,36,1,(4)),(9,26,2,(1,1)),(3,50,8,(8,8,1,6,6,3,3,2)),(7,94,2,(3,6)),(8,39,9,(1,3,4,9,5,5,9,6,6)),(2,22,7,(5,4,7,2,7,8,1)),(4,88,4,(9,6,3,4)),(5,46,8,(5,2,7,8,9,9,3,4)),(3,23,6,(6,8,2,8,4,7)),(7,76,6,(6,7,4,7,4,5)),(5,77,6,(6,8,4,3,7,5)),(7,34,3,(2,2,9))),((1,3),(2,4),(3,5),(4,3),(5,2),(6,3),(7,6),(8,4),(9,3),(10,2),(11,4),(12,5),(13,3),(14,6),(15,6),(16,9),(17,6),(18,8)))" +
				",(52,2,((2,50,1,(1)),(1,81,2,(1,1)),(1,95,2,(1,1)),(1,39,2,(2,2)),(1,66,2,(2,2)),(2,64,1,(2)),(2,49,2,(1,2)),(2,29,2,(1,1)),(2,91,2,(2,2)),(1,47,2,(1,1)),(2,87,2,(2,1)),(2,37,2,(2,1)),(1,35,2,(1,2)),(1,60,2,(1,2)),(2,74,1,(1)),(1,69,2,(1,1)),(1,32,2,(1,1)),(2,48,1,(1)),(1,52,1,(1)),(1,76,2,(1,1)),(1,78,2,(2,1)),(1,31,1,(1)),(2,55,1,(1)),(1,61,1,(2)),(2,67,1,(2)),(2,51,1,(1)),(2,82,2,(2,1)),(2,53,2,(2,2)),(2,75,2,(2,1)),(1,24,2,(1,2)),(1,28,1,(1)),(1,38,1,(2)),(1,57,2,(1,2)),(2,80,1,(1)),(2,65,1,(2)),(2,30,1,(2)),(2,25,1,(1)),(1,56,2,(2,2)),(1,79,2,(1,1)),(1,73,1,(2)),(2,59,2,(1,1)),(1,22,2,(2,2)),(1,85,1,(2)),(2,34,2,(2,1)),(2,21,2,(1,1)),(2,23,2,(2,2)),(2,41,2,(2,1)),(1,45,1,(2)),(1,89,1,(1)),(2,43,2,(2,2)),(1,27,2,(2,2)),(1,99,2,(2,2))),((1,4),(2,7)))" +
				",(50,9,((4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9)),(4,83,9,(5,3,4,6,8,7,2,1,9))),((1,6),(2,6),(3,6),(4,6),(5,6),(6,6),(7,6),(8,6),(9,6)))" +
				",(4,2,((1,100,2,(2,1)),(2,50,2,(1,2)),(2,60,1,(1)),(1,70,1,(2))),((1,1),(2,2)))" +
				",(2,2,((1,100,2,(2,1)),(2,90,2,(1,2))),((1,1),(2,1)))" +
				",(9,2,((1,100,2,(1,2)),(2,80,2,(2,1)),(1,90,1,(1)),(2,40,1,(2)),(2,50,1,(1)),(1,60,1,(2)),(2,75,1,(1)),(1,95,1,(1)),(2,30,1,(2))),((1,3),(2,4)))" +
				",(4,2,((1,110,2,(1,2)),(2,150,1,(1)),(1,80,2,(2,1)),(2,60,1,(1))),((1,2),(2,2)))" +
				",(61,13,((2,97,9,(1,2,8,8,2,4,8,6,4)),(9,55,4,(6,2,2,8)),(3,41,6,(3,3,2,8,3,3)),(9,49,1,(8)),(2,86,9,(7,9,6,1,8,7,2,2,6)),(6,68,7,(6,2,9,4,6,2,1)),(9,95,3,(1,9,1)),(7,70,4,(3,4,5,2)),(9,64,1,(4)),(2,93,2,(7,2)),(7,59,3,(6,2,9)),(8,96,7,(6,8,7,5,3,7,6)),(5,29,7,(8,4,9,3,1,8,7)),(5,44,7,(8,9,9,4,9,1,6)),(6,34,1,(7)),(1,57,9,(6,7,2,7,5,5,2,8,4)),(3,22,6,(7,5,2,7,1,2)),(2,36,6,(7,1,9,7,9,8)),(9,83,8,(9,4,8,4,1,5,8,2)),(2,47,1,(8)),(4,85,4,(4,6,7,1)),(6,35,8,(3,9,9,9,8,4,4,8)),(4,37,2,(8,4)),(1,77,6,(9,3,8,9,4,1)),(6,84,5,(1,2,9,6,2)),(7,27,8,(3,2,2,8,5,9,5,6)),(2,45,4,(7,2,2,7)),(1,58,9,(8,7,6,3,6,3,4,1,6)),(1,65,6,(6,8,5,5,1,8)),(2,92,9,(4,8,8,6,2,5,7,9,7)),(2,38,5,(5,8,5,3,1)),(2,91,5,(8,2,4,2,3)),(9,90,5,(9,1,6,8,4)),(4,89,6,(9,1,2,9,7,5)),(3,48,4,(9,7,1,2)),(4,52,9,(6,5,2,7,8,9,3,5,1)),(9,53,6,(4,7,9,8,6,3)),(8,31,3,(8,4,8)),(6,43,6,(1,2,9,2,9,4)),(9,82,3,(2,4,2)),(2,99,8,(8,7,3,2,1,1,9,7)),(2,25,1,(3)),(9,33,7,(3,3,4,3,9,8,7)),(7,79,4,(7,5,5,2)),(8,63,8,(3,6,8,3,5,5,1,6)),(9,74,2,(5,7)),(1,88,5,(4,8,4,5,3)),(2,61,6,(1,3,2,2,2,9)),(7,81,7,(5,3,5,6,7,5,3)),(9,56,8,(8,4,1,2,4,2,9,2)),(6,24,6,(2,1,7,6,1,3)),(8,50,9,(2,5,5,7,3,8,9,7,4)),(5,26,3,(4,9,5)),(9,60,2,(4,3)),(9,54,4,(4,4,4,8)),(7,66,2,(3,8)),(7,69,9,(9,3,3,8,7,1,6,2,8)),(3,76,9,(2,7,8,1,3,1,9,7,5)),(8,21,7,(4,7,4,4,2,7,9)),(7,32,3,(3,5,6)),(9,72,4,(8,5,9,8))),((1,7),(2,1),(3,1),(4,5),(5,8),(6,2),(7,5),(8,3),(9,1),(10,8),(11,9),(12,3),(13,9)))";
		String inputs[] = input.split(":");
		GetStudentCount(Integer.parseInt(inputs[0]), inputs[1]);
		System.out.println(Arrays.toString(output1));
	}
}
